package _binary_tree

import common.TreeNode
import org.junit.Assert
import org.junit.Test

/**
https://leetcode.cn/problems/kth-smallest-element-in-a-bst/description/

```
230. 二叉搜索树中第 K 小的元素
给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 小的元素（从 1 开始计数）。

示例 1：
![kthtree1.jpg](https://assets.leetcode.com/uploads/2021/01/28/kthtree1.jpg)
输入：root = [3,1,4,null,2], k = 1
输出：1

示例 2：
![kthtree2.jpg](https://assets.leetcode.com/uploads/2021/01/28/kthtree2.jpg)
输入：root = [5,3,6,2,4,null,null,1], k = 3
输出：3
```

 */
class leetcode_230 {

    @Test
    fun test_1() {
        val n1 = TreeNode(1)
        val n2 = TreeNode(2)
        val n3 = TreeNode(3)
        val n4 = TreeNode(4)
        val root: TreeNode = n3
        n3.left = n1
        n3.right = n4
        n1.right = n2
        val actual = kthSmallest(root, 1)
        val expected = 1
        Assert.assertEquals(expected, actual)
    }

    @Test
    fun test_2() {
        val n1 = TreeNode(1)
        val n2 = TreeNode(2)
        val n3 = TreeNode(3)
        val n4 = TreeNode(4)
        val n5 = TreeNode(5)
        val n6 = TreeNode(6)
        val root: TreeNode = n5
        n5.left = n3
        n5.right = n6
        n3.left = n2
        n3.right = n4
        n2.left = n1
        val actual = kthSmallest(root, 3)
        val expected = 3
        Assert.assertEquals(expected, actual)
    }


    private fun kthSmallest(root: TreeNode?, k: Int): Int {
        return kthSmallest1(root, k)
        // kthSmallest2(root, k)
    }

    private fun kthSmallest1(root: TreeNode?, k: Int): Int {
        /**
        思路：二叉树 - 中序遍历
        利用中序遍历二叉搜索树得到第k-1个，就是目标值。
         */
        // https://www.cnblogs.com/wwj99/p/12310924.html

        f(root, k)
        return target
    }

    var target: Int = -1
    var count: Int = 0
    fun f(root: TreeNode?, k: Int) {
        // 1 确定函数参数以及返回值

        // 2 确定终止条件
        if (root == null) {
            return
        }

        // 3 确定单层递归的方向：左中右
        // 左
        f(root.left, k)

        // 中
        count++
        if (count == k) {
            target = root.`val`
            // println("found count=$count,${root.`val`}")
            return
        }
        //  println("count=$count,${root.`val`}")

        // 右
        f(root.right, k)
    }


    private fun kthSmallest2(root: TreeNode?, k: Int): Int {
        /**
        思路：二叉树 - 中序遍历
        利用中序遍历二叉搜索树得到结果集，那么 第 i= k-1 个 就是目标值。
         */
        // https://www.cnblogs.com/wwj99/p/12310924.html
        f(root)
        val target: Int = result[k - 1]
        return target
    }

    var result: ArrayList<Int> = ArrayList()
    private fun f(root: TreeNode?) {
        // 1 确定函数参数以及返回值

        // 2 确定终止条件
        if (root == null) {
            return
        }

        // 3 确定单层递归的逻辑:中序（左中右）
        f(root.left)
        result.add(root.`val`)
        f(root.right)
    }
}